package _04_arithExpression;

import _04_linkedStack.SinglyLinkedStack;
import _04_seqStack.SeqStack;
import _04_seqStack.Stack;

public class ArithExpression {
    
    // 运算符集合
    private static Operators operators;
    
    static {
        operators = new Operators();
    }
    
    public ArithExpression(String infix) {
        // 如果中缀表达式正确
        if (right(infix)) {
            // 转换成后缀表达
            String postfix = toPostfix(infix);
            // 后缀表达式字符串
            System.out.println("postfix = \"" + postfix + "\"");
            System.out.println("value = " + toValue(postfix));
        }
    }
    
    private boolean right(String infix) {
        // TODO Auto-generated method stub
        Stack<Character> stack = new SeqStack<Character>();
        for (int i = 0; i < infix.length(); i++) {
            char ch = infix.charAt(i);
            if (ch == '(') {
                stack.push('(');
            } else if (ch == ')') {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else {
                    System.out.println("多余的)");
                    return false;
                }
            }
        }
        if (stack.isEmpty()) {
            return true;
        } else {
            System.out.println("缺少)");
            return false;
        }
    }

    // 将中缀表达式字符串转换成后缀表达式字符串，以1+2*(3-4)+56为例，应该返回1 2 3 4 - * + 5 6 +
    /* 
       转换过程分析：
       1是数字，则写入后缀表达式字符串，postfix:1 , stack:
       +是运算符，由于当前运算符栈为空，则入栈postfix:1 , stack:+
       2是数字，写入后缀表达式字符串，postfix:1 2 , stack:+
       *是运算符，由于比上一个入栈的运算符即栈顶运算符的优先级高，所以入栈postfix:1 2 , stack:+ *
       (是左括号，也要入栈，postfix:1 2 , stack:+ * (
       3是数字，写入后缀表达式字符串，postfix:1 2 3 , stack:+ * (
       -是运算符，由于此时栈顶元素是(，则继续入栈，postfix:1 2 3 , stack:+ * ( -
       4是数字，写入后缀表达式字符串，postfix:1 2 3 4 , stack:+ * ( -
       )是右括号，运算符从栈顶依次出栈，直到(出栈后停止出栈，运算符出栈后依次写入后缀表达式字符串中，postfix:1 2 3 4 - , stack:+ *
       +是运算符，要使其优先级>=栈顶运算符时才可入栈，那么* +依次出栈并写入后缀表达式字符串中，postfix:1 2 3 4 - * + , stack:+
       5是数字，写入后缀表达式字符串，postfix:1 2 3 4 - * + 5 , stack:+
       6是数字，写入后缀表达式字符串，postfix:1 2 3 4 - * + 56 , stack:+
       结束符，运算符从栈顶依次出栈并写入后缀表达式字符串中，postfix:1 2 3 4 - * + 56 +, stack:
     */
    // 这里自作聪明用String类型来做，殊不知每+=一次都要新创建一个新的String对象，空间占用大
    private String toPostfix(String infix) {
        // TODO Auto-generated method stub
        // 运算符栈，采用顺序栈
        Stack<String> stack = new SeqStack<String>();
        // 后缀表达式字符串
        String postfix = "";
        int i = 0;
        String str = null;
        while (i < infix.length()) {
            char ch = infix.charAt(i);
            String op = this.operators.isOperator(infix, i);
            // System.out.println(ch + ", " + op + ", " + postfix + ", " + stack);  // 用于过程监控
            // 判断infix字符串第i~？的子串能否匹配到操作数
            if (op != null) {
                // 如果op的优先级大于等于栈顶运算符优先级（值小的优先级高）
                // System.out.println(this.operators.getPriority()[this.operators.indexOf(op)] + ", " + this.operators.getPriority()[this.operators.indexOf(stack.peek())]);
                boolean judge = this.operators.getPriority()[this.operators.indexOf(op)] <= this.operators.getPriority()[this.operators.indexOf(stack.peek())];
                // 如果op优先级小于栈顶且栈不为空，出栈直到op优先级大于或等于栈顶，如果栈顶元素为"("，则必须等遇到")"才能出栈，栈顶元素为"("时，在此出不允许出栈
                while (!judge && !stack.isEmpty() && !stack.peek().equals("(")) {
                    // 写入栈顶运算符并用空格隔开不同的运算符
                    postfix += stack.peek() + " ";
                    stack.pop();
                }
                // 如果栈为空，或op优先级大于或等于栈顶运算符，或栈顶元素为"("时，入栈
                if (stack.isEmpty() || judge || stack.peek().equals("(")) {
                    stack.push(op);
                }
                i += op.length();
            } else if (ch >= '0' && ch <= '9') {
                while (i < infix.length() && (ch = infix.charAt(i)) >= '0' && ch <= '9') {
                    postfix += ch;
                    i++;
                }
                // 用空格隔开每个数
                postfix += " ";
            } else if (ch == '(') {
                stack.push(ch + "");
                i++;
            } else if (ch == ')') {
                while (!stack.isEmpty() && !stack.peek().equals("(")) {
                    // 写入栈顶运算符并用空格隔开不同的运算符
                    postfix += stack.peek() + " ";
                    stack.pop();
                }
                stack.pop();
                i++;
            } else {
                i++;
            }
        }
        while (!stack.isEmpty()) {
            // 写入栈顶运算符并用空格隔开不同的运算符
            postfix += stack.peek() + " ";
            stack.pop();
        }
        return postfix;
    }
    
    public int toValue(String postfix) {
        // TODO Auto-generated method stub
        // 操作数栈，采用单链栈
        Stack<Integer> stack = new SinglyLinkedStack<Integer>();
        int i = 0;
        while (i < postfix.length()) {
            char ch = postfix.charAt(i);
            if (ch >= '0' && ch <= '9') {
                int value = 0;
                while (i < postfix.length() && (ch = postfix.charAt(i)) >= '0' && ch <= '9') {
                    value = value * 10 + ch - '0';
                    i++;
                }
                // System.out.println(i + ", " + value);    // 用于过程监控
                stack.push(value);
            } else {
                String op = operators.isOperator(postfix, i);
                if (op == null) {
                    i++;
                } else {
                    // 出栈两个数
                    int x = stack.pop();
                    int y = stack.pop();
                    // 将运算结果入栈用于下一步运算，注意是y operate x，而不是x operate y
                    stack.push(operators.operate(y, x, op));;
                    i += op.length();
                }
                // System.out.println(i + ", " + op);   // 用于过程监控
            }
            // System.out.println(stack);   // 用于过程监控
        }
        return stack.peek();
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ArithExpression ae1 = new ArithExpression("1 + 2 * (3 * 4 - 6) + 56");
        ArithExpression ae2 = new ArithExpression("1 + 2 ** (3 - 4) + 56");
        ArithExpression ae3 = new ArithExpression("((1+2)*3+4)");
        ArithExpression ae4 = new ArithExpression("123+10*(45-50+20/((35-25)*2+10)-11");
        ArithExpression ae5 = new ArithExpression("45+(10-15)*(25+35)/(60-40))-11");
    }

}
